Diffie-Hellman 密钥交换&ElGamal协议的安全密钥交换

发表于 | 更新于 | 分类于

Diffie-Hellman 密钥交换&ElGamal协议的安全密钥交换

离散对数问题

在整数中，离散对数是一种基于同余运算和原根的一种对数运算。而在实数中对数的定义 $log_b a$ 是指对于给定的 a 和 b，有一个数 x，使得$b^{x}$ = a。相同地在任何群 G中可为所有整数 k定义一个幂数为$b^{k}$，而离散对数是 $log_b a$指使得$b^{x}$ = a的 整数 k。

离散对数在一些特殊情况下可以快速计算。然而，通常没有具非常效率的方法来计算它们。公钥密码学中几个重要算法的基础，是假设寻找离散对数的问题解，在仔细选择过的群中，并不存在有效率的求解算法。

Diffie-Hellman 密钥交换

Diffie-Hellman是一种建立密钥的方法，而不是加密方法。然而，它所产生的密钥可用于加密、进一步的密钥管理或任何其它的加密方式。Diffie-Hellman密钥交换算法及其优化首次发表的公开密钥算法出现在Diffie和Hellman的论文中，这篇影响深远的论文奠定了公开密钥密码编码学。

这种密钥交换技术的目的在于使得两个用户安全地交换一个秘密密钥以便用于以后的报文加密. Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度 。

主要过程

  • 所有用户都知道的全局参数

    • 大素数q
    • g : 用来模q的原始根

  • 每个用户生成自己的公钥(对于用户A)

    • 选择一个密钥，(私钥)：数字 $x_{A}$<q
    • 计算公钥：$y_{A}=g^{x_{A}}\mod q$
    • 每个用户公开公钥

  • 则用户A&B共享的会话密钥是$K_{AB}$

    ​ (B可以计算出来)

    ​ (A可以计算出来)

From WIKI：

最简单，最早提出的这个协议使用一个质数p的整数模n乘法群)以及其原根g。下面展示这个算法，绿色表示非秘密信息, 红色粗体表示秘密信息

TIM图片20180518085502

  1. 爱丽丝和鲍伯写上一个有限循环群 G 和它的一个生成元 g。 （这通常在协议开始很久以前就已经规定好； g是公开的，并可以被所有的攻击者看到。）
  2. 爱丽丝选择一个随机自然数 a(很大) 并且将 $g^{a}\mod p$（大素数）发送给鲍伯。
  3. 鲍伯选择一个随机自然数 b （很大）并且将 $g^{b}\mod p$发送给爱丽丝。
  4. 爱丽丝 计算 $(g^{b})^{a} \mod p$ 。
  5. 鲍伯 计算 $(g^{a})^{b} \mod p$ 。

爱丽丝和鲍伯就同时协商出群元素$g^{ab}$，它可以被用作共享秘密。$(g^{b})^{a}$和$(g^{a})^{b}$因为群乘法交换的。

算法解释

爱丽丝和鲍伯最终都得到了同样的值，因为在模p下$g^{ab}$和 $g^{ba}$ 相等。 注意a, b 和 $g^{ab}= g^{ba} \mod p$ 是秘密的。 其他所有的值 – p, g, $g^{a} \mod p$, 以及 $g^{b}\mod p $– 都可以在公共信道上传递。 一旦爱丽丝和鲍伯得出了公共秘密，他们就可以把它用作对称密钥，以进行双方的加密通讯，因为这个密钥只有他们才能得到。

Elgamal密码体制

1984年，T.Elgamal提出了一种基于离散对数的公开密钥体制，是一个基于迪菲-赫尔曼密钥交换的非对称加密算法。ElGamal密码体系应用于一些技术标准中，如数字签名标准（DSS）和S/MIME电子邮件标准。与Diffie-Hellman一样，ElGamal的系统用户也是共同选择一个素数q，$g$是q的素跟。

算法描述

ElGamal加密算法由三部分组成：密钥生成、加密和解密。

密钥生成

密钥生成步骤如下：

  • Alice利用生成元 $g$ 产生一个 q,阶循环群 $G$,的有效描述。该循环群需要满足一定的安全性质。
  • Alice从 $\{1,\cdots,q-1\}$中随机选择一个 $x$。
  • Alice计算 $h:=g^{x} \mod q $。
  • Alice公开$h$,以及 $G,q,g$ 的描述作为其公钥，并保留 $x$ 作为其私钥。私钥必须保密。
加密

其他用户可以通过Alice的公钥进行加密。

用Alice的公钥 $(G,q,g,h)$向她加密一条消息 m的加密算法工作方式如下：

  • 将信息表示成一个整数M，其中$1\leq M \leq q-1$，以分组密码序列的方式来发送信息，其中每个分块的长度不小于整数q。

  • Bob从 $\{1,\cdots,q-1\}$ 随机选择一个 $y$。（私钥）

  • 然后计算 密钥$K=h^{y} \mod q$。（会话密钥）

  • 将M加密成明文对$(C_{1}，C_{2})$，其中

    $C_{1}=g^{y} \mod q ; C_{2}=K\cdot M \mod q $（公钥，加密的信息）

解密

Alice利用自己的私钥进行解密。

  • 得到密钥：$K=(C_{1})^{x} \mod q$

  • 得到消息$M = (C_{2}K^{-1}) \mod q$

    如果信息必须分组，然后以加密的密钥块序列发送，那么每个分块要有唯一的x（私钥）。如果x用于多个分块，则利用信息的分块$M_{1}$，攻击者会计算出其他块。

ElGamal的安全性是基于计算离散对数的困难性之上。

参考资料

[1]维基百科编者. 迪菲-赫尔曼密钥交换[G/OL]. 维基百科, 2018(20180503)[2018-05-03]. https://zh.wikipedia.org/w/index.php?title=%E8%BF%AA%E8%8F%B2-%E8%B5%AB%E7%88%BE%E6%9B%BC%E5%AF%86%E9%91%B0%E4%BA%A4%E6%8F%9B&oldid=49408565.

[2]《密码编码学与网络安全 原理与实践》（第6版）斯托林斯著

[3]维基百科编者. ElGamal加密算法[G/OL]. 维基百科, 2016(20161214)[2016-12-14]. https://zh.wikipedia.org/w/index.php?title=ElGamal%E5%8A%A0%E5%AF%86%E7%AE%97%E6%B3%95&oldid=42453545.